{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Word Break 单词拆分\n",
    "\n",
    "### 难度：Medium\n",
    "\n",
    "## 刷题内容\n",
    "\n",
    "> 原题链接\n",
    "\n",
    " - 中文：https://leetcode-cn.com/problems/word-break/description/\n",
    " - 英文：https://leetcode.com/problems/word-break/\n",
    " \n",
    "> 内容描述\n",
    "\n",
    "```\n",
    "给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。\n",
    "\n",
    "说明：\n",
    "\n",
    "1、拆分时可以重复使用字典中的单词。\n",
    "2、你可以假设字典中没有重复的单词。\n",
    "\n",
    "示例 1：\n",
    "输入: s = \"leetcode\", wordDict = [\"leet\", \"code\"]\n",
    "输出: true\n",
    "解释: 返回 true 因为 \"leetcode\" 可以被拆分成 \"leet code\"。\n",
    "\n",
    "示例 2：\n",
    "输入: s = \"applepenapple\", wordDict = [\"apple\", \"pen\"]\n",
    "输出: true\n",
    "解释: 返回 true 因为 \"applepenapple\" 可以被拆分成 \"apple pen apple\"。\n",
    "     注意你可以重复使用字典中的单词。\n",
    "\n",
    "示例 3：\n",
    "输入: s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"]\n",
    "输出: false\n",
    "```\n",
    "\n",
    "## 解题方案\n",
    "\n",
    "> 思路 1\n",
    "\n",
    " - 字符串 S ，它的长度为 N ，如果 S 能够被 字典集合（dict）中的单词拼接而成，那么所要满足的条件为：\n",
    "     - F(0, N) = F(0, i) && F(i, j) && F(j, N)\n",
    "     - 这样，如果我们想知道某个子串是否可由 Dict 中的几个单词拼接而成就可以用这样的方式得到结果（满足条件为True，不满足条件为 False）存入到一个 boolean 数组的对应位置上，这样，最后 boolean 数组的最后一位就是 F(0, N) 的值，为 True 表示这个字符串 S 可以由 Dict 中的单词拼接，否则是不行的。\n",
    " - AC 代码如下"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # 参数校验\n",
    "        if s is None or len(s) < 1 or wordDict is None or len(wordDict) < 1:\n",
    "            return False\n",
    "        # 标记是否匹配，match[i] 表示 [0, i-1] 都匹配\n",
    "        length = len(s)\n",
    "        match = [False for i in range(length + 1)]\n",
    "        match[0] = True\n",
    "        \n",
    "        for i in range(1, length +1):\n",
    "            for j in range(i):\n",
    "                if match[j] and s[j:i] in wordDict:\n",
    "                    match[i] = True\n",
    "                    break\n",
    "        return match[length]\n",
    "\n",
    "\n",
    "sss = Solution()\n",
    "s = \"leetcode\"\n",
    "wordDict = [\"leet\", \"code\"]\n",
    "print(sss.wordBreak(s, wordDict))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "> 思路 2\n",
    "\n",
    " - **ok[i] 表示 s[:i] 是不是存在于我们的字典中。**\n",
    " - 原理类似于我们上面的 思路 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        ok = [True]\n",
    "        for i in range(1, len(s)+1):\n",
    "            ok += [any(ok[j] and s[j:i] in wordDict for j in range(i))]\n",
    "        return ok[-1]\n",
    "    \n",
    "sss = Solution()\n",
    "s = \"leetcode\"\n",
    "wordDict = [\"leet\", \"code\"]\n",
    "print(sss.wordBreak(s, wordDict))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "但是往list里面加数据的方法有快有慢，下面是对比：\n",
    "\n",
    "```python\n",
    ">>> from timeit import timeit\n",
    ">>> timeit('x.append(1)', 'x = []', number=10000000)\n",
    "1.9880003412529277\n",
    ">>> timeit('x += 1,',     'x = []', number=10000000)\n",
    "1.2676891852971721\n",
    ">>> timeit('x += [1]',    'x = []', number=10000000)\n",
    "3.361207239950204\n",
    "```\n",
    "\n",
    "因此我们可以将代码直接换成下面的格式：\n",
    "\n",
    "```python\n",
    "ok += any(ok[j] and s[j:i] in wordDict for j in range(i))  # 会报错\n",
    "```\n",
    "\n",
    "但是这样会报错，TypeError: 'bool' object is not iterable，因此bool类型数据不能这样加，别的可以（list类型本身当然要注意哈）\n",
    "\n",
    "因此在这个例子中我们这样："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        ok = [True]\n",
    "        for i in range(1, len(s)+1):\n",
    "            ok += any(ok[j] and s[j:i] in wordDict for j in range(i)),\n",
    "        return ok[-1]\n",
    "    \n",
    "sss = Solution()\n",
    "s = \"leetcode\"\n",
    "wordDict = [\"leet\", \"code\"]\n",
    "print(sss.wordBreak(s, wordDict))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
